package 越长越合法

// need被破坏无法正确判断
//
//	func validSubstringCount(word1 string, word2 string) int64 {
//		n1 := len(word1)
//		n2 := len(word2)
//		ans := 0
//		if n2 > n1 {
//			return 0
//		}
//		need := map[string]int{}
//		for _, c := range word2 {
//			need[string(c)]++
//		}
//		left := 0
//		for right, c := range word1 {
//			need[string(c)]--1
//			for len(need) == 0 && left <= right {
//				need[string(c)]--
//				left++
//			}
//			ans += right - left + 1
//		}
//		return int64(ans)
//
// }
func validSubstringCount(word1 string, word2 string) int64 {
	n1, n2 := len(word1), len(word2)
	if n2 > n1 {
		return 0 // 长度不足，直接返回0
	}

	// 1. 统计word2的字符需求（need）和所需种类数（required）
	need := make(map[rune]int)
	for _, c := range word2 {
		need[c]++
	}
	required := len(need) // 需要满足的字符种类数

	// 2. 滑动窗口相关变量
	window := make(map[rune]int) // 窗口内字符频率
	have := 0                    // 已满足（window[c] >= need[c]）的种类数
	left := 0
	var ans int64 = 0

	// 3. 右指针遍历word1
	for _, c := range word1 {
		// 更新窗口内当前字符的频率
		window[c]++

		// 若当前字符满足需求（频率达标），且是第一次达标，更新have
		if window[c] == need[c] {
			have++
		}

		// 4. 当窗口满足所有需求（have == required），尝试缩小左边界
		for have == required {
			// 以right为结尾的有效子串数量 = left+1（起点可从0到left）
			ans += int64(left + 1)

			// 移动左指针，减少窗口内左字符的频率
			leftC := rune(word1[left])
			window[leftC]--

			// 若左字符频率从达标变为不达标，更新have
			if window[leftC] == need[leftC]-1 {
				have--
			}

			left++
		}
	}

	return ans
}
